package premiere_partie;

import java.util.ArrayList;

public class MotBienParenthese {

	/**
	 * Methode renvoyant tous les mots bien parenthésé avec n paires de parentheses
	 * 
	 * @param n entier, nombre de paire de parentheses
	 * @return liste de mot bien parenthésés de taille 2n
	 * 
	 * complexité de liste.add("") = Θ(1)
	 * premier for complexite = Θ(n)
	 * n appelle recursifs de la methode
	 * Cn = Cn-1 + n
	 * D'après le cours on obtient avec cette formule une complexité = Θ(n)
	 * 
	 * deuxieme for complexite = Θ(n)
	 * for imbriqué complexité = Θ(n)
	 * appelle a la methode w complexité = Θ(1)
	 * complexité du if = Θ(1)
	 * list.add(res) complexité = Θ(1)
	 * 
	 * complexité totale du deuxieme for = Θ(n²)
	 */
	public static ArrayList<String> enumMotsBP(int n){
		ArrayList<String> motBPprec = new ArrayList<String>();		// Liste de tous les mots bien parenthésés de taille < n
		ArrayList<String> liste = new ArrayList<String>();			// Liste de tous les mots bien parenthésés de taille == n
		if(n==0)
			liste.add("");
		else {
			for(int i=0; i<n ; i++)									// On ajoute les mot bien parenthésés (taille < n).
				motBPprec.addAll(enumMotsBP(i));
			for (int j=0 ; j<motBPprec.size() ; j++ ){				// Pour tous les mots bien parenthésés (parcours du premier au dernier)
				String res ="";
				for (int k=motBPprec.size()-1 ; k>=0 ; k--){		// Pour tous les mots bien parenthésés (parcours du dernier au premier)
					res = w(motBPprec.get(j),motBPprec.get(k));		// On utilise le constructeur des mbp
					if(res.length() == 2*n ) 						// Si le mot est de la bonne taille ( = n)
						liste.add(res);								// On l'ajoute a la liste
				}
			}
		}
		return liste;
	}

	/**
	 * Constructeur mot bien parentheses
	 * @param u un mot bien parenthésé
	 * @param v un mot bien parenthésé
	 * @return la chaine (u)v
	 * 
	 * complexité constante
	 */
	public static String w(String u, String v){
		return "(" + u + ")" + v;
	}

	/**
	 * Methode retournant le nombre de mot bien parenthésé de taille 2n
	 * @param n, le nombre de paire de parenthèses
	 * @return le nombre de mot bien parenthésé de taille 2n
	 * 
	 * if a une complexité Θ(1)
	 * la formule se calcul en Θ(1)
	 * C'est une methode recursive sur n donc
	 * Complexité linéaire O(n)
	 */
	public static double catalan (int n) {
		if( n-1==0 )
			return 1;
		double a = 2*(n-1)+1;
		return ( (2*(a)) / (n+1) ) * catalan(n-1);
	}

	/**
	 * Methode qui affiche la vitesse de calcul en ms de la methode catalan(i) pour chaque 0<i<=n
	 * @param n le nombre de paire de parenthèse 
	 */
	public static void testCatalan(int n){
		double catalani;
		long t0;
		long temps;
		for(int i=1;i<=n;i++){
			t0 = System.currentTimeMillis();
			catalani = catalan(i);
			temps= System.currentTimeMillis()-t0;
			//if(i>n-n/100)								// Decommenter si n grand
				System.out.println("Temps de calcul du "+i+"ème nombre de Catalan : "+temps + "(res : " + catalani + ")");
		}
	}

	/**
	 * Deuxième methode retournant le nombre de mot bien parenthésé de taille 2n
	 * @param n le nombre de paire de parenthèses
	 * @return le nombre de mot bien parenthésé de taille 2n
	 * 
	 * On a deux boucle imbriquées
	 * Complexité quadratique
	 */
	public static double catalan2(int n){
		long tab[] = new long[n+1];
		tab[0]=1;
		for( int i=0; i<n ; i++) {
			for (int j=0; j<=i; j++) {
				tab[i+1] += tab[j]*tab[i-j]; 
			}
		}
		return tab[n];
	}
	
	/**
	 * Methode qui affiche la vitesse de calcul en ms de la methode catalan2(i) pour chaque 0<i<=n
	 * @param n le nombre de paire de parenthèse 
	 */
	public static void testCatalan2(int n){
		double catalani;
		long t0;
		long temps;
		for(int i=1;i<=n;i++){
			t0 = System.currentTimeMillis();
			catalani=catalan2(i);
			temps= System.currentTimeMillis()-t0;
			//if(i>n-n/100)
				System.out.println("Temps de calcul du "+i+"ème nombre de Catalan : "+temps + "(res : " + catalani + ")");
		}
	}//testCatalan2

	/**
	 * Methode testant si le mot passé en parametre est bien parenthésé
	 * Utilisation de deux compteurs
	 * @param s le mot a tester
	 * @return true si s est bien parenthésé
	 * 
	 * On parcours dans s entierement dans la boucle while, complexité Θ(n)
	 * s.charAt(i) est de complexité Θ(1)
	 * le troisieme if est de complexité Θ(1)
	 * Complexité totale Θ(n)
	 */
	public static boolean testBienP(String s) {
		int nbo=0, nbf=0, i=0;
		
		// Le mot n'est pas bien parenthésé si il commence
		// par une parenthèse fermante
		if (s.length() != 0 && s.charAt(0) == ')')
			return false;
		
		while ( i < s.length())
		{
			char c =s.charAt(i);
			if(  c == '(' ){
				nbo++;
			}
			else if ( c == ')' ){
				nbf++;
			}
			if (nbo - nbf < 0 )
				return false;
			i++;
		}
		return (nbo - nbf == 0 );
	}

	/**
	 * Affichage d'un mot bien parenthese avec une indentation correcte 
	 * @param s un mot bien parenthésé
	 * 
	 * On parcours dans s entierement dans la boucle while, complexité Θ(n)
	 * s.charAt(i) est de complexité Θ(1)
	 * Cas '('
	 * la complexité des boucles for dans le if sont en  O(n/2)
	 * car il y a au plus n/2 tabulations ( cas des mots BP)
	 * De meme pour')'
	 * Cas du troisieme if : complexité en Θ(1)
	 * 
	 * complexité totale en O(n²/2)
	 */
	public static void indent(String s) {
		int i=0, tabu=0;
		while( i < s.length() ){
			char c = s.charAt(i);
			if( c == '(' ){						// Cas d'une parenthese ouvrante
				System.out.println();
				for(int j=0 ; j<tabu ; j++)
					System.out.print("\t");
				System.out.println(c);
				for(int j=0 ; j<tabu ; j++)
					System.out.print("\t");
				tabu++;
			}
			else if( c == ')' ){				// Cas d'une parenthese fermante
				tabu--;
				System.out.println();
				for(int j=0 ; j<tabu ; j++)
					System.out.print("\t");
				System.out.println(c);
				for(int j=0 ; j<tabu-1 ; j++)
					System.out.print("\t");
			}
			else {								// Cas d'un autre caractère
				System.out.print(c);
			}
			i++;
		}
	}

	/**
	 * Methode qui renvoie la profondeur des parentheses du mot s
	 * @param s un mot bien parenthese
	 * @return la profondeur des parentheses du mot s
	 * 
	 * On parcours dans s entierement dans la boucle while, complexité Θ(n)
	 * s.charAt(i) est de complexité Θ(1)
	 * complexité totale Θ(n)
	 */
	public static int profondeur (String s) {
		int prof=0, i=0, max=0;
		while( i < s.length() ){
			char c = s.charAt(i);
			if( c == '(')
				prof ++;
			else if( c == ')'){
				if (max < prof)
					max = prof;
				prof --;
			}
			i++;
		}
		return max;
	}

	
	/* Hors programme*/
	
	/**
	 * Retourne tous les mots BP de taille < n (C_i)
	 * @param n entier, nombre de paire de parenthese
	 * @return mot BP de taille < n
	 */
	public static ArrayList<String> enumMotsBPinf(int n){
		ArrayList<String> motBPprec = new ArrayList<String>();
		ArrayList<String> liste = new ArrayList<String>();
		if(n==0)
			liste.add("");
		else {
			for(int i=0; i<n ; i++)
				motBPprec.addAll(enumMotsBP(i));
			for (int j=0 ; j<motBPprec.size() ; j++ ){
				String res ="";
				for (int k=motBPprec.size()-1 ; k>=0 ; k--){
					res = w(motBPprec.get(j),motBPprec.get(k));
					if(res.length() < 2*n ) 
						liste.add(res);
				}
			}
		}
		return liste;
	}

	/**
	 * Methode retournant le nombre de mot BP uniques de taille < n
	 * @param n entier
	 * @return liste de mot BP
	 */
	public static int catalan3(int n) {
		ArrayList<String> str = enumMotsBPinf(n);			// Appel recursif a enumMotsBPinf
		ArrayList<String> cptg = new ArrayList<String>();	// Liste vide permettant de retourner des mots uniques
		int i=0;
		boolean estdsliste = false;
		while ( i<str.size() ) {
			estdsliste = false;
			for ( int j=0 ; j< cptg.size() ; j++) {
				if(cptg.get(j).equals(str.get(i)))
					estdsliste = true;
			}
			if(!estdsliste)
				cptg.add(str.get(i));
			i++;
		}
		return cptg.size();
	}
}
